(1) Field of the Invention
The present invention relates to the field of memory accessing technology for the storage and retrieval of data and/or instructions from a memory unit. Specifically, the present invention relates to the field of memory cache technology employed to increase the speed and execution time predictability of instruction code processing or data processing.
(2) Prior Art
Among the many elements of a computer system are found a central processing unit (CPU), memory storage units (which may be RAM or ROM or otherwise), and interface and control logic units that couple the CPU to the memory storage units for accessing and processing of data and instructions. Generally, each time the CPU processes an instruction it must access a memory storage unit to gain desired data for processing or to obtain the execution instructions themselves, the opcodes, which reside in memory. The CPU is constantly interfacing with the memory storage units. Recent developments in computer technology have offered a variety of different types of memory storage units which are adapted for different functions and have different characteristics. Specifically, use of a cache memory unit and associated logic has become extremely popular because of the versatility, efficiency, and high speed accessing offered by the cache memory. Cache memories that store data used in a program are called data cache memory and cache memories that store program instructions, opcodes, are called instruction cache memories.
Opcodes or Instructions as Data
Machine code (assembly code) is the program code that a microprocessor interprets and processes directly. Each instruction of a program executed by a microprocessor is represented as data within a computer memory and is called instruction data. In order to execute a program, the microprocessor must read the memory to access the program steps or microcode instructions. These instructions are processed on a sequential basis and therefore the memory unit is generally accessed in such a way. The below syntax is an example of instruction data and program data: EQU LOAD C, 08H.
The above instructs the microprocessor to load the value of 08H into a register called "C." The instruction, LOAD, to load register C, will have an associated numeric value which represents the load instruction and this value must be stored in memory. This value is called instruction data because it is data that represents the instruction. For sake of illustration, assume that the microprocessor instruction for loading register "C" with an immediate value is decoded into the value, 068H. In memory, the value of 068H is stored and is called instruction data. The value 08H is called program data because it is the data that will be loaded into register "C," but it does not represent an instruction. In memory, this value is located adjacent to the associated instruction data. Each value has an associated address of memory. The below illustrates how these values might be stored in a typical computer memory.
______________________________________ Address Data ______________________________________ 0001 068H 0002 08H ______________________________________
Where address 0001 holds the instruction data for the load instruction, 068H, while address 0002 contains the program data for the value to be loaded into the register, 08H.
An Instruction Cache
The instruction cache is typically a small sized and specially designed memory unit designed for high speed access to the CPU of a microprocessor in order to provide the microprocessor with some program instructions. Typically, the instruction cache is of limited size because of the constraints of interfacing the cache in the same chip as the CPU; a typical instruction cache may be 1/100th the size of the main (external) memory unit. The cache memory is designed to specially interface with the CPU so that the CPU can access the instructions stored in the cache at very high speeds verses the relative long instruction accessing time required of other, external, memory units. Many cache units are located structurally within the chip containing the microprocessor unit for high speed accessing.
An instruction cache is filled with the addresses and instruction data of the instructions that the CPU will probably execute on a routine or cyclic basis. These instructions are placed into the cache memory from the external memory (or generated by the CPU and placed into the cache memory) typically during the execution of a program. That is, the most recently processed instructions, determined by monitoring the instruction flow executed by the CPU, are placed into the instruction cache memory. New instructions are placed or replaced into the instruction cache and tagged for identification while older instructions (i.e., sections of the program code not accessed over a given time period) are slowly "aged out" or removed from the instruction cache. The instructions placed within the cache are also tagged with a unique identifier that is related to the effective memory address associated with the instruction of the external memory unit.
Cache operations function on the theory that many computer programs frequently utilize a relatively small percentage of program code on a cyclic basis and those commonly used instructions will end up located within the high speed cache memory providing efficient access. During program execution when the CPU desires to execute program code stored in memory, a special cache logic unit which is part of the cache first scans the contents of the instruction cache memory unit to determine if the desired address is located within the high speed instruction cache. If so, the instructions are accessed via the instruction cache utilizing the tag identifier and the position of the instruction data within the cache. In this case external memory access is not required to execute this program code and therefore the delay associated with external memory access is avoided. Each time instructions are accessed via the instruction cache a significant amount of time is saved by avoiding the delay associated with the external memory access. In the event that the desired instructions are not within the data cache, an instruction cache logic unit will indicate that a "cache miss" has occurred associated with the access instruction. When a cache miss occurs, the desired data must be accessed from, or to, the external memory which is usually not associated with the structural location of the cache memory unit. This accessing of the external memory takes longer than a cache memory access.
A prior art cache system is illustrated in the block diagram of FIG. 1.0. The external memory unit 60 is illustrated coupled to interface control unit 14 which provides controlled access to the external memory 60. A high speed limited size instruction cache unit 10 is illustrated coupled to the logic unit 14. The high speed cache unit is coupled to a microprocessor instruction fetch unit 50 via a cache control unit 12 which controls accessing to the cache between microprocessor instructions and determines whether or not the requested microprocessor instructions reside in the cache. The instruction cache memory 10 may be associated within the cache logic unit 12. The microprocessor instruction fetch unit 50, the logic unit 12 and the high speed cache 10 are all located within the chip of the microprocessor 5. Because of this location, and other special characteristics, the instruction cache memory 10 allows high speed, efficient interface to the microprocessor.
When the microprocessor requests to execute an instruction, the address of the instruction is first examined to determine if the instruction may be accessed via the instruction cache 10 by comparing the address of the instruction to the tags of the cache memory 10. If the instruction is available from instruction cache 10, then the cache 10 will rapidly supply the program instruction and no external memory access to memory 60 is required. If the program instruction is not found within the instruction cache 10 then a cache miss will be generated and the instruction is fetched through the external memory 60. When the requested instruction is obtained via the logic unit 14, it is forwarded to the microprocessor instruction processing unit for execution. The fetched instruction is also placed into the instruction cache 10 and tagged to be made available for subsequent use. Each time an instruction can be accessed from the cache, only a small amount of time is expended for the instruction access. On the other hand, each time an instruction must be accessed via the external memory 60, a large access delay is encountered which decreases overall processing speed and efficiency.
The Need for Predictability
It should be noted from the above discussions that the exact accessing location of a particular instruction (i.e., within cache or external memory) is not always known because the instruction cache 10 is updated on a real-time basis with the most recently used instructions stored in the cache and others aged out and replaced according to the cache logic. Using such a cache system, a programmer at the time the code is developed will not know the exact memory unit from which particular instructions will be accessed. Since each accessing location has different associated delays (i.e., cache accessing is very rapid while external memory accessing is very slow) a programmer will not know the exact execution time for any particular code segment. The execution time will depend on the time the microprocessor takes to execute the instruction (which is generally known) plus the time the system expends to access the required instructions and associated data from memory (which depends on whether the cache memory or the external memory is accessed).
There are instances when a particular section of program code must execute within some given timing window. For instance, assuming an embedded microprocessor is implemented within a laser printer. Certain update routines that create an image for printing must operate within a given high speed timing window in order to keep up with specialized printing and imaging hardware. In these applications, the programmer must be assured that critical program code sections that generate the print image fully execute within the given high speed time constraint. Given the unpredictable nature of the contents of the instruction cache, the prior art systems will not assure that critical program code sections fully execute within a predictable timing window. What is needed is a cache system that provides high speed and predictable execution time of critical program code sections while allowing other sections of the program code to operate normally with the instruction cache. The present invention offers such capability.
One prior art system implemented to provide execution time predictability shuts down the instruction cache completely during program execution. By shutting down the instruction cache, all processed instruction must be accessed via the external memory and therefore the accessing time is known for all instructions. However, this prior art system suffers from poor processor performance because the instruction cache is disabled and external memory is used for all accessing. Such poor performance is not desirable in most microprocessor applications. Further, many applications require that the time critical code sections operate as rapidly as possible. This prior art system of disabling the instruction cache will not satisfy applications requiring high speed execution of the critical code sections. What is needed is a system that offers high speed execution time as well as predictability of the critical program code sections. The present invention offers such capability.
Another prior art system for providing execution time predictability is illustrated in FIG. 2. FIG. 2 illustrates an instruction cache unit 10 that is separated into two different sections. Section 21 is the top section and contains cache entries 1 to 10 while section 22 is the bottom section containing cache entries 11 to 20. This prior art system offers execution time predictability by placing those sections of the program that require time critical processing into section 21 while section 22 can be utilized for other caching operations. Critical program code is loaded into the upper section 21 of the instruction cache 10 and the other section 22 remains available for other caching purposes. In effect, this prior art system creates two caches, one for time critical portions and one for the other program sections.
In operation this prior art system of FIG. 2 is disadvantageous because the program code must specify which instruction cache (21 or 22) is to be used for each program code section to be executed. If the cache portion is not specifically identified and indicated by the programmer, the time critical section in the cache can be overwritten. The bookkeeping required to track each time critical section versus the non-time critical sections is complex. Special instructions must be developed in order to differentiate between the two cache sections 21 or 22 used with each program code section. Each instruction address also must be specially identified (coded) to include the proper cache section associated with that instruction. Each time a time critical section is entered or exited, the programmer must employ special instructions to direct proper use of either cache section 21 and cache section 22. Also, if a mistake in programming is made and the wrong cache section is associated with the time critical code, the result is that processing performance will be severely degraded because each executed instruction will generate a cache miss because the wrong cache is being referenced.
What is needed is a system that offers high speed execution as well as execution time predictability that is also transparent and easy to use for a programmer. That is, what is needed is a system that is very straightforward to utilize for a programmer and that does not require a programmer to indicate and specify each cache location for particular critical and noncritical program code routines. What is needed is a system like the above that can be implemented without overly costly modifications to existing instruction cache systems. The present invention offers such capability.
Accordingly, it is an object of the present invention to provide a method and apparatus for providing an instruction cache locking scheme. A further object of the present invention is to provide execution time predictability of time critical routines at the highest possible execution time in order to increase processing speed and efficiency. Another object of the present invention is to provide the above in a system that is generally transparent to the program code and that does not require a variety of additional or complex instructions or address codes. Another object of the present invention is to provide instruction cache flexibility by allowing certain portions of the instruction cache to provide caching operations for time critical program routines while allowing other portions of the instruction cache to process other program sections. It is an object of the present invention to implement the advantages of the above instruction cache locking scheme without overly complex and advanced circuits so that the instruction cache locking scheme can be implemented in existing caching systems without undue expense or modification. It is appreciated that other objects of the present invention not specifically enumerated herein will become apparent in discussions to follow.